package com.learn.algorithm.exercises.nowcoder;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author wangxing
 * @version 2020/7/10 17:53 Administrator
 */
public class SimulationStack {
    /**
     * 牛妹在练习打字，现在按照时间顺序给出牛妹按下的键
     * （以字符串形式给出,'<'代表回退backspace，其余字符均是牛妹打的字符，字符只包含小写字母与'<'），
     * 牛妹想知道最后在屏幕上显示的文本内容是什么。
     * 在文本内容为空的时候也可以按回退backspace（在这种情况下没有任何效果）。
     *
     * @param s string字符串
     * @return string字符串
     */
    public String Typing(String s) {
        // write code here
        char[] charArr = s.toCharArray();
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : charArr) {
            if (c == '<') {
                if (!stack.isEmpty()) {
                    stack.removeFirst();
                }
            } else {
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.getLast());
            stack.removeLast();
        }
        return result.toString();
    }

    public String Typing2(String s) {
        // write code here
        char[] charArr = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c : charArr) {
            if (c == '<') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        Stack<Character> stack2 = new Stack<>();
        while (!stack.isEmpty()) {
            stack2.push(stack.pop());
        }
        while (!stack2.isEmpty()) {
            result.append(stack2.pop());
        }
        return result.toString();
    }

}
